% Aufgaben Lösungen.tex
\documentclass{article}

\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage[T1]{fontenc}

\renewcommand{\labelenumi}{\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii})}


\begin{document}
\textbf{Aufgabe:}\\
Die Übergangstabelle eines DEA siehe wie folgt aus:\\
%--------------------------------------------
\begin{tabular}{cll}
|         & 0       & 1                   \\[0.5ex]
                                                    \hline
                                                    \\[-1ex]
$\rightarrow q_{1}$   & $q_{2}$ & $q_{1}$   \\
$q_{2}$   & $q_{3}$ & $q_{3}$   \\
$^{\ast}q_{3}$   & $q_{3}$ & $q_{2}$		
\end{tabular}
%--------------------------------------------
\\
Die Graph eines DEA sehe wie folgt aus:
\\
\\
\\

%\begin{center}
%-----------------------------------------------------------------------------------------------------------
    \unitlength=4pt
    \begin{picture}(20, 14)(0,-7)
    \gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=4}
    \thinlines
    %\node[Nmarks=ifr](C)(75,-30){all}
    \node[Nmarks=i,iangle=180](A1)(0,0){$q_{1}$}
    \node(A2)(20,0){$q_{2}$}
    \node[Nmarks=r](A3)(40,0){$q_{3}$}
    \drawedge(A1,A2){$0$}
    \drawedge(A2,A1){$1$}
    \drawedge(A2,A3){$0$}
    \drawedge(A3,A2){$1$}
    \drawloop[loopangle=90](A1){$1$}
    \drawloop[loopangle=0](A3){$0$}
    \end{picture}
%-----------------------------------------------------------------------------------------------------------
%\end{center}



a) Formulieren Sie alle regulären Ausdrücke $R^{(0)}_{ij}$. \textit{Hinweis:} Stellen Sie sich den Zustand $q_{i}$ so vor, als handle es sich um den Zustand mit der ganzzahligen Nummer $i$.
\newline\newline
b) Formulieren Sie alle regulären Ausdrücke $R^{(1)}_{ij}$. Versuchen Sie die Ausdrücke so weit wie möglich zu vereinfachen.
\newline\newline
c) Formulieren Sie alle regulären Ausdrücke $R^{(2)}_{ij}$. Versuchen Sie die Ausdrücke so weit wie möglich zu vereinfachen.
\newline\newline
d) Formulieren Sie einen regulären Ausdruck für die Sprache des Automaten.
\newline\newline
e) Konstruieren Sie das Übergangsdiagramm für den DEA, und geben sie einen regulären Ausdruck für die Sprache des Automaten an, indem sie $q_{2}$ eleminieren.\\
\\
\textbf{Lösung:}\newline\newline
a) Wir müssen alle $R^{(0)}_{ij}$  für alle  $i,j \in \{1,2,3\}$ bestimmen. Anders ausgedrückt: Wie kommt man von Zustand $i$ zu Zustand $j$ ohne über einen Zustand zu gehen, der höher als 0 ist. Da die Nummerierung der Zustände bei $1$ beginnt, bedeutet das nichts anderes als: Wie komme ich von Zustand $i$ ohne Umweg zu Zustand $j$. Dies führt zu folgenden 9 zu berechnenden $R^{(0)}_{ij}$:
\begin{enumerate}
	\item 
	$R^{(0)}_{11} = \varepsilon + 1$ \newline
	Von Zustand 1 nach Zustand 1 über keinen höheren Zustand als 0 gibt es 2 mögliche Pfade. Keine Eingabe ($\varepsilon$), oder Eingabe von $1$.
	\item 
	$R^{(0)}_{12} = 0$ \newline
	Von Zustand 1 nach Zustand 2 über keinen höheren Zustand als 0 gibt es genau einen möglichen Pfad. Die Eingabe von $0$.
	\item 
	$R^{(0)}_{13} = \emptyset$ \newline
	Von Zustand 1 nach Zustand 3 über keinen höheren Zustand als 0 gibt es keinen Pfad $\rightarrow\emptyset$.\newline
	Dies ist der erste für den, dem Automaten äquivalenten, Teilausdruck, da er vom Start- zum akzeptierenden Zustand führt.
	\item 
	$R^{(0)}_{21} = 1$ \newline
	Vom Zustand 2 nach Zustand 1 über keinen höheren Zustand als 0 gibt es genau einen Pfad, mit $1$ beschriftet.
	\item 
	$R^{(0)}_{22} = \varepsilon$ \newline
	Vom Zustand 2 zu sich selbst über keinen höheren Zustand als 0 gibt es genau einen Pfad, mit $\varepsilon$ beschriftet.
	\item 
	$R^{(0)}_{23} = 0$ \newline
	Vom Zustand 2 zum Zustand 3 über keinen höheren Zustand als 0 gibt es genau einen Pfad, mit $0$ beschriftet
	\item $R^{(0)}_{31} = \emptyset$ \newline
	Vom Zustand 3 zum Zustand 1 über keinen höheren Zustand als 0 gibt es keinen Pfad $\rightarrow\emptyset$.
	\item 
	$R^{(0)}_{32} = 1$ \newline
	Vom Zustand 3 zum Zustand 2 über keinen höheren Zustand als 0 gibt es genau einen Pfad, mit $1$ beschriftet.
	\item 
	$R^{(0)}_{33} = \varepsilon + 0$ \newline
	Vom Zustand 3 zu sich selbst über keinen Pfad höher als 0 gibt es zwei Pfade, die Eingabe von $\varepsilon$ oder $0$.
\end{enumerate}
b) Für die Berechnung aller $R^{(1)}_{ij}$ muss nur noch die folgende Formel angewendet werden: 
$R^{(k)}_{ij} = R^{(k-1)}_{ij} + R^{(k-1)}_{ik} (R^{(k-1)}_{kk})^{\ast} R^{(k-1)}_{kj}$ \newline
In diesem Fall ist $k=1$ was zu $k-1 = 0$ führt. Und diese $R^{(0)}_{ij}$ wurden alle in a) schon gebildet. Folglich können die folgenden 9 $R^{(k)}_{ij}$ leicht gebildet werden und müssen dann nur noch richtig vereinfacht werden.\newline
Vereinfacht wird nach den Regeln:
\begin{itemize}
	\item 
	$(\varepsilon + R)^{\ast} = R^{\ast}$
	\item 
	$(\varepsilon + 1)1^{\ast} = 1^{\ast}$
	\item 
	$\emptyset R = R \emptyset = \emptyset$
	\item 
	$\emptyset + R = R + \emptyset = R$
\end{itemize}
\begin{enumerate}
  \item 
  \begin{tabbing}
  $R^{(1)}_{11}$\=$=R^{(1-1)}_{11} + R^{(1-1)}_{11} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{11}$\\
  \>$=(\varepsilon + 1) + (\varepsilon + 1)(\varepsilon + 1)^{\ast} (\varepsilon + 1)$\\
  \>$=(\varepsilon + 1) + (\varepsilon + 1)^{\ast}$\\
  \>$=(\varepsilon + 1)^{\ast}$\\
 	\>$=1^{\ast}$
 	\end{tabbing}
 	
  \item	
  \begin{tabbing}
	$R^{(1)}_{12}$\=$=R^{(1-1)}_{12} + R^{(1-1)}_{11} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{12}$\\
	\>$= 0 + (\varepsilon + 1)(\varepsilon + 1)^{\ast}0$\\
	\>$= 0 + 1^{\ast}0$\\
	\>$= 1^{\ast}0$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(1)}_{13}$\=$=R^{(1-1)}_{13} + R^{(1-1)}_{11} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{13}$\\
	\>$= \emptyset + (\varepsilon + 1)(\varepsilon + 1)^{\ast}\emptyset$\\
	\>$= \emptyset + \emptyset$\\
	\>$= \emptyset$\\
	\end{tabbing}
	Dies ist der zweite für den, dem Automaten äquivalenten, Teilausdruck, da er vom Start- zum akzeptierenden Zustand führt.
	
	\item 
	\begin{tabbing}
	$R^{(1)}_{21}$\=$=R^{(1-1)}_{21} + R^{(1-1)}_{21} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{11}$\\
	\>$= 1 + 1 (\varepsilon + 1)^{\ast}(\varepsilon + 1))$\\
	\>$= 1 + 11^{\ast}$\\
	\>$= 11^{\ast}$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(1)}_{22}$\=$=R^{(1-1)}_{22} + R^{(1-1)}_{21} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{12}$\\
	\>$= \varepsilon + 1 (\varepsilon + 1)^{\ast} 0$\\
	\>$= \varepsilon + 11^{\ast}0$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(1)}_{23}$\=$=R^{(1-1)}_{23} + R^{(1-1)}_{21} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{13}$\\
	\>$= 0 + 1 (\varepsilon +1)^{\ast} \emptyset$\\
	\>$= 0$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(1)}_{31}$\=$=R^{(1-1)}_{31} + R^{(1-1)}_{31} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{13}$\\
	\>$= \emptyset + \emptyset (\varepsilon + 1)^{\ast} \emptyset$\\
	\>$= \emptyset$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(1)}_{32}$\=$=R^{(1-1)}_{32} + R^{(1-1)}_{31} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{12}$\\
	\>$= 1 + \emptyset(\varepsilon + 1)^{\ast} 0$\\
	\>$= 1 $
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(1)}_{33} $\=$ =R^{(1-1)}_{33} + R^{(1-1)}_{31} (R^{(1-1)}_{11})^{\ast} R^{(1-1)}_{13}$\\
	\>$= (\varepsilon + 0) + \emptyset(\varepsilon + 1)^{\ast} \emptyset$\\
	\>$= \varepsilon + 0$
	\end{tabbing}
\end{enumerate}

c)Für die Berechnung aller $R^{(2)}_{ij}$ muss wieder die Formel angewendet werden, nur ist $k$ statt $1$ diesmal $2$\\
$R^{(k)}_{ij} = R^{(k-1)}_{ij} + R^{(k-1)}_{ik} (R^{(k-1)}_{kk})^{\ast} R^{(k-1)}_{kj}$ \\
\begin{enumerate}
	\item 
	\begin{tabbing}
	$R^{(2)}_{11} $\=$= R^{(1)}_{11} + R^{(1)}_{12} (R^{(1)}_{22})^{\ast} R^{(1)}_{21}$ \\
	\>$= 1^{\ast} + 1^{\ast}0 (\varepsilon + 11^{\ast}0)^{\ast}11^{\ast}$\\
	\>$= 1^{\ast} + 1^{\ast}0(11^{\ast}0)^{\ast}11^{\ast}$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(2)}_{12} $\=$= R^{(1)}_{12} + R^{(1)}_{12} (R^{(1)}_{22})^{\ast} R^{(1)}_{22}$ \\
	\>$= 1^{\ast}0 + 1^{\ast}0 (\varepsilon + 11^{\ast}0)^{\ast} (\varepsilon + 11^{\ast}0)$\\
	\>$= 1^{\ast}0 (\varepsilon + 11^{\ast}0)^{\ast}$\\
	\>$= 1^{\ast}0(11^{\ast}0)^{\ast}$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(2)}_{13} $\=$= R^{(1)}_{13} + R^{(1)}_{12} (R^{(1)}_{22})^{\ast} R^{(1)}_{23}$ \\
	\>$= \emptyset + 1^{\ast}0 (\varepsilon + 11^{\ast}0)^{\ast} 0$\\
	\>$= 1^{\ast}0(11^{\ast}0)^{\ast}0$\\
	\end{tabbing}
	Dies ist der dritte für den, dem Automaten äquivalenten, Teilausdruck, da er vom Start- zum akzeptierenden Zustand führt.
	
	\item 
	\begin{tabbing}
	$R^{(2)}_{21} $\=$= R^{(1)}_{21} + R^{(1)}_{22} (R^{(1)}_{22})^{\ast} R^{(1)}_{21}$ \\
	\>$= 11^{\ast} + (\varepsilon + 11^{\ast}0)(\varepsilon + 11^{\ast}0)^{\ast}11^{\ast}$\\
	\>$= (11^{\ast}0)^{\ast}11^{\ast}$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(2)}_{22} $\=$= R^{(1)}_{22} + R^{(1)}_{22} (R^{(1)}_{22})^{\ast} R^{(1)}_{22}$ \\
	\>$	= (\varepsilon + 11^{\ast}0) + (\varepsilon + 11^{\ast}0)(\varepsilon + 11^{\ast}0)^{\ast}(\varepsilon + 11^{\ast}0)$\\
	\>$	= (\varepsilon + 11^{\ast}0)^{\ast}$\\
	\>$	= (11^{\ast}0)^{\ast}$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(2)}_{23} $\=$= R^{(1)}_{23} + R^{(1)}_{22} (R^{(1)}_{22})^{\ast} R^{(1)}_{23}$ \\
	\>$= 0 + (\varepsilon + 11^{\ast}0)(\varepsilon + 11^{\ast}0)^{\ast}0$\\
	\>$= 0 + (11^{\ast}0)^{\ast}0$\\
	\>$= (11^{\ast}0)^{\ast}0$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(2)}_{31} $\=$= R^{(1)}_{31} + R^{(1)}_{32} (R^{(1)}_{22})^{\ast} R^{(1)}_{21}$ \\
	\>$= \emptyset + 1(\varepsilon + 11^{\ast}0)^{\ast}11^{\ast}$\\
	\>$= 1(\varepsilon + 11^{\ast}0)^{\ast}11^{\ast}$\\
	\>$= 1(11^{\ast}0)^{\ast}11^{\ast}$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(2)}_{32} $\=$= R^{(1)}_{32} + R^{(1)}_{32} (R^{(1)}_{22})^{\ast} R^{(1)}_{22}$ \\
	\>$= 1 + 1(\varepsilon + 11^{\ast}0)^{\ast}(\varepsilon + 11^{\ast}0)$\\
	\>$= 1(11^{\ast}0)^{\ast}$
	\end{tabbing}
	
	\item 
	\begin{tabbing}
	$R^{(2)}_{33} $\=$= R^{(1)}_{33} + R^{(1)}_{32} (R^{(1)}_{22})^{\ast} R^{(1)}_{23}$ \\
	\>$= (\varepsilon + 0) + 1(\varepsilon + 11^{\ast}0)^{\ast}0$\\
	\>$= \varepsilon + 0 + 1(11^{\ast}0)^{\ast}0)$
	\end{tabbing}
\end{enumerate}
\newpage
d) Um den Ausdruck zu formulieren, der die selbe Sprache beschreibt, wieder DEA, müssen alle Teilausdrücke $R^{(3)}_{ij}$ für alle $i\in q_{0}$ und $j\in F$ (alle Ausdrücke die vom Startzustand zu einem akzeptierenden Zustand führen) vereinigt werden. Das betrifft bei diesem DEA nur jenen Ausdruck, der von Zustand 1($q_{0}$) zu Zustand 3 ($q_{2}$) führt. Genauer:\newline\newline

$R_{DEA} = R^{(3)}_{13}$\newline\newline

Also muss noch der Ausdruck $R^{(3)}_{13}$ gebildet werden:\newline\newline
\begin{tabbing}
$R^{(3)}_{13} $\=$= R^{(2)}_{13} + R^{(2)}_{13}(R^{(2)}_{33})^{\ast}R^{(2)}_{33}$\\
\>$= (1^{\ast}0(11^{\ast}0)^{\ast}0) + (1^{\ast}0(11^{\ast}0)^{\ast})((11^{\ast}0)^{\ast})^{\ast}(11^{\ast}0)^{\ast}0$\\
\>$= (1^{\ast}0(11^{\ast}0)^{\ast}0) + (1^{\ast}0(11^{\ast}0)^{\ast})(11^{\ast}0)^{\ast}(11^{\ast}0)^{\ast}0$\\
\>$= (1^{\ast}0(11^{\ast}0)^{\ast}0) +(1^{\ast}0(11^{\ast}0)^{\ast})(11^{\ast}0)^{\ast}0$\\
\>$= 1^{\ast}0(11^{\ast}0)^{\ast}0 + 1^{\ast}0(11^{\ast}0)^{\ast}(11^{\ast}0)^{\ast}0$\\
\>$= 1^{\ast}0(11^{\ast}0)^{\ast}0$
\end{tabbing}
\newpage
e) 
\unitlength=4pt
\begin{picture}(20, 14)(0,-7)
\gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=4}
\thinlines
%\node[Nmarks=ifr](C)(75,-30){all}
\node[Nmarks=i,iangle=180](A1)(0,0){$q_{1}$}
\node(A2)(20,0){$q_{2}$}
\node[Nmarks=r](A3)(40,0){$q_{3}$}
\drawedge(A1,A2){$0$}
\drawedge(A2,A1){$1$}
\drawedge(A2,A3){$0$}
\drawedge(A3,A2){$1$}
\drawloop[loopangle=90](A1){$1$}
\drawloop[loopangle=0](A3){$0$}
\end{picture}


Auf den Übergangspfeilen des DEAs stehen im Moment noch Zeichenreihen. Diese werden als erstes in reguläre Ausdrücke umgeschrieben. Danach sieht der DEA mit regulären Ausdrücken auf den Pfeilen wie folgt aus \emph{reguläre Ausdrücke seien hier mal fett gedruckt}:
\\
\unitlength=4pt
\begin{picture}(20, 14)(0,-7)
\gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=4}
\thinlines
%\node[Nmarks=ifr](C)(75,-30){all}
\node[Nmarks=i,iangle=180](A1)(0,0){$q_{1}$}
\node(A2)(20,0){$q_{2}$}
\node[Nmarks=r](A3)(40,0){$q_{3}$}
\drawedge(A1,A2){$\textbf{0}$}
\drawedge(A2,A1){$\textbf{1}$}
\drawedge(A2,A3){$\textbf{0}$}
\drawedge(A3,A2){$\textbf{1}$}
\drawloop[loopangle=90](A1){$\textbf{1}$}
\drawloop[loopangle=0](A3){$\textbf{0}$}
\end{picture}
\\
Man beachte, dass der reguläre Ausdruck, der die Zeichenkette bestehend aus $\{a\}$ beschreibt, $\textbf{a}$ lautet. Deshalb hat sich am Graphen selbst nichts geändert. Um nun den Zustand $q_{2}$ zu eliminieren werden wie im Buch beschrieben, die r. Audrücke die zum Zustand $q_{2}$ führen (seien \textbf{a}), die vom Zustand $q_{2}$ zu sich selbst führen (seien \textbf{b}) und die, die vom Zustand weg führen (seien \textbf{c}) aneinander gereiht, in der Form \textbf{abc}. Da es noch Pfade gibt, die genau in die andere Richtung verlaufen, muss das ganze auch von $q_{3}$ nach $q_{1}$ in der Gegenrichtung gemacht werden. Weiter hin muss man beachten, dass ein Pfad jeweils von $q_{1}$ über $q_{2}$ zurück zu $q_{1}$ und einer von $q_{3}$ über $q_{2}$ zurück zu $q_{3}$ führt, mit den jewiligen Pfaden des Zustands zu sich selbst vereinigt werden. Dies führt zu dem folgenden Übergangsgraphen:
\\
\begin{center}
\unitlength=4pt
\begin{picture}(20, 14)(0,-7)
\gasset{Nw=5,Nh=5,Nmr=2.5,curvedepth=4}
\thinlines
%\node[Nmarks=ifr](C)(75,-30){all}
\node[Nmarks=i,iangle=180](A1)(-20,0){$q_{1}$}
%\node(A2)(20,0){$q_{2}$}
\node[Nmarks=r](A3)(20,0){$q_{3}$}
\drawedge(A1,A3){$\textbf{00}$}

\drawedge(A3,A1){$\textbf{11}$}

\drawloop[loopangle=90](A1){$\textbf{1 + 01}$}
\drawloop[loopangle=0](A3){$\textbf{0 + 10}$}
\end{picture}
\end{center}

\begin{center}
\textbf{$(1 + 01)^{\ast}00((0 + 10) + (11(1 + 01)^{\ast}00))^{\ast}$}
\end{center}

\textbf{Erklärung:} Sind wir in $q_{1}$, kann beliebig oft (auch 0 mal) $(1 + 01)$ in der Zeichenreihe kommen, das bewirkt keine Zustandsänderung. Deshalb ist der erste Teil $(1 + 01)^{\ast}$. Um eine Zustandsänderung zu bewirken muss ein $00$ kommen, um in $q_{3}$ zu gelangen. deshalb wir dem ersten Teilausdruck ein $00$ angehängt, was zu $(1 + 01)^{\ast}00$ führt. In $q_{3}$ sind wir im akzeptierenden Zustand. Jetzt kann beliebig oft (auch 0 mal) \textit{entweder} $(0 + 10)$ in der Zeichenreihe kommen(was den Zustand nicht verändert - der Automat bleibt in $q_{3}$), \textit{oder} $11$ (führt von $q_{3}$ zu $q_{1}$), gefolgt von beliebig oft $(1 + 01)$, gefolgt von $00$ - das ergibt den Teilausdruck, der von $q_{3}$ über $q_{1}$ zurück zu $q_{3}$ führt, womit wir wieder im akzeptierenden Zustand wären. Dieser Teilausdruck lautet also $(11(1 + 01)^{\ast}00)$. Da beliebig oft von $q_{3}$ über $q_{1}$ wieder zu $q_{3}$ gewechselt werden darf wird dem ganzen noch ein Sternchen angehängt: $(11(1 + 01)^{\ast}00)^{\ast}$.\\
Jetzt weden einfach die beiden Teilausdrücke (1. der, der von $q_{1}$ zu $q_{3}$; 2. der von $q_{3}$ über $q_{1}$ zuück zu $q_{3}$) aneinander gehängt, was den fertigen Ausdruck ergibt:
\begin{equation}
(1 + 01)^{\ast}00((0 + 10) + (11(1 + 01)^{\ast}00))^{\ast}
\end{equation}



\end{document}